1. Field of the Invention
The present invention relates to a communications system in which data is transmitted from a sender to a receiver through a transmission line. In particular, the present invention relates to a synchronization control method and a system for establishing a bit-to-bit correspondence of data between a sender and a receiver.
2. Description of the Related Art
The internet, which continues growing rapidly, is convenient on one hand, but its security is quite uncertain on the other hand. There is an increasing need for cryptographic technologies in order to maintain the secrecy of communications. Cryptographic schemes currently used in general can be classified into two categories: secret key cryptography such as DES (Data Encryption Standard) and triple DES, and public key cryptography such as RSA (Rivest Shamir Adleman) and ECC (Elliptic Curve Cryptography). However, these techniques are cryptographic communication methods that ensure the security of communication based on the “complexity of computation” and are always fraught with the danger that ciphertext could be broken with the advent of an algorithm enabling a vast amount of computation or a cryptanalysis algorithm. With such a background, quantum key distribution (QKD) systems receive attention as the cryptographic key distribution technologies that are “absolutely immune against eavesdropping.”
In QKD, a photon is generally used as a communication medium, and transmission is performed by superimposing information on the quantum state (such as polarization and phase) of the photon. An eavesdropper present on a transmission line intercepts the information by tapping photons being transmitted, or by other methods. However, according to the Heisenberg's uncertainty principle, it is impossible to perfectly return the quantum state of a photon once observed to its original state before observation, and resultantly, a change occurs in the statistic values of received data detected by a legitimate receiver. By monitoring this change, the receiver can detect the presence or absence of an eavesdropper on the transmission line.
In the case of a quantum key distribution method utilizing the phase of a photon, a transmitter/sender and a receiver (hereinafter, referred to as “Alice” and “Bob” respectively, as have been used traditionally) constitute an optical interferometer. Alice and Bob individually perform random phase modulation on each of single photons. Output of 0 or 1 is obtained depending on the difference between the depths of these phase modulations. Thereafter, Alice and Bob check part of the respective conditions they used when the output data were measured against each other, whereby the same bit string can be shared between Alice and Bob finally. Next, the most typical quantum key distribution algorithm by the name of BB84 protocol will be described briefly (see Bennett and Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing,” IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, pp. 175-179).
FIG. 1 is a schematic diagram showing a concept of a quantum key distribution method according to the BB84 protocol. Here, it is assumed that Alice 141 and Bob 143 are connected through an optical transmission line 142.
According to this method, Alice 141 has two random number sources, one of which (random number 1) provides random numbers representing cryptographic key data (0/1), and the other one of which (random number 2) is for determining the way of coding the information of the random number 1. In quantum key distribution methods utilizing the phase of a photon, two coding sets are used: a coding set for representing a set of phases of 0 and π that correspond to “0” and “1” in the cryptographic key, respectively (hereinafter, this set will be referred to as “+basis”), and a coding set for representing a set of phases of π/2 and 3π/2 that correspond to “0” and “1” in the cryptographic key, respectively (hereinafter, this set will be referred to as “x basis”. The random number 2 is used to make a selection from the two bases. That is, any one of the four types of modulation (0,π/2, π, 3π/2) is randomly performed on each of single photons, which are then sent to Bob one by one.
On the other hand, Bob 143 has a random number source (random number 3) corresponding to the bases and uses it to decode the single photons sent from Alice 141. When a value of the random number 3 is “0”, a modulation of 0 phase (+basis) is performed on a photon. When a value of the random number 3 is “1”,  a modulation of π/2 phase (x basis) is performed on a photon. Here, random numbers obtained as the output of the optical interferometer are collectively referred to as random number 4.
When a basis Alice used in modulation is the same as a basis Bob used in modulation (random number 2=random number 3), Bob can correctly detect a value of the random number 1 (random number 1=random number 4). When a basis Alice used in modulation is different from a basis Bob used in modulation (random number 2≠ random number 3), Bob randomly obtains a value of 0 or 1 for the random number 4, independently of a value of the random number 1. Since each of the random numbers 1, 2 and 3 is a collection of random numbers varying with each one bit, the probability that a basis match occurs and the probability that no basis match occurs are both 50%. However, since those bits corresponding to the non-matching bases are removed through basis reconciliation at a subsequent stage, Alice 141 and Bob 143 can share a bit string composed of 0s and 1s based on the random number 1.
However, the bit string thus shared contains errors attributable to the transmission line 142 and/or the receiver, and therefore, to correct these errors, error correction processing is needed. In addition to this, errors also occur in the shared bit string when an eavesdropper present on the transmission line intercepts the photon information. Accordingly, to share a cryptographic key for final use, not only the error correction processing for correcting errors, privacy amplification is also needed to reduce the amount of information that conceivably has been intercepted, based on the frequency of errors (error rate). Incidentally, methods of estimating “the amount of information that conceivably has been intercepted” are described in the following documents:
N. Lutkenhaus, “Estimates for practical quantum cryptography,” Physical Review A, Vol. 59, No. 5, p. 3301 (hereinafter, this document will be referred to as Lutkenhaus); and
M. Williamson, “Eavesdropping on practical quantum cryptography,” quantum-ph/0211155 (hereinafter, this document will be referred to as Williamson).
FIG. 2 is a flowchart showing a flow of quantum key generation in general. Among original random numbers for a cryptographic key (source of key) sent from Alice, most amount of the information is lost through quantum key distribution (single-photon transmission) S1. A key shared between Alice and Bob at this stage is called a raw key. The key that has lost approximately one half the mount of information after basis reconciliation S2 mentioned above, is called a sifted key. Thereafter, error correction S3 for correcting errors that were contained in the key at the stage of quantum key distribution is carried out, followed by privacy amplification S4 for eliminating the amount of information that conceivably has been leaked to an eavesdropper. Then, the remains are made to be a final key, which will be actually used as a cryptographic key. There have been proposed several techniques for sharing a quantum cryptographic key as described above.
For example, Japanese Patent Application Unexamined Publication No. 2000-174747 discloses a quantum cryptographic device that allows a sender and a receiver to share a secret key by using a quantum channel and a classical channel. Specifically, the sender extracts a bit value from a random number table, performs fine-modulation on an optical pulse in accordance with the extracted bit value, and sends the optical pulse through the quantum channel. The receiver independently extracts a bit value from another random number table, re-modulates the received optical pulse in accordance with the extracted bit value, and notifies the sender through the classical channel whether or not a photon is detected. The sender constructs a random number table using only the bit values for which a photon has been detected at the receiver. Thus, each of the sender and receiver stores the common random number table. Further, to check the presence/absence of eavesdropping, an appropriate number of check bits are extracted from each common random number table, and these are checked against each other through the classical channel. If a sufficient number of bits match, a bit string excluding the check bits is used as a shared secret key.
Japanese Patent Application Unexamined Publication No. 2004-112278 discloses a quantum key distribution method that improves the efficiency in generating a shared key by eliminating data errors caused by the propagation of a signal along a quantum communication path (quantum channel). Specifically, through the quantum communication path, a sender transmits a photon in a quantum state that is specified by a number from a random-number sequence (transmission data) and a randomly determined basis (transmission code). A receiver observes the received photon and obtains reception data that is specified by the result of this observation and a randomly determined basis (reception code. Thereafter, a procedure through a public communication path is carried out so that only those bits corresponding to the matching bases remain, whereby shared information is stored in each of the sender and receiver. Subsequently, through the public communication path, the sender transmits error correction information with a predetermined number of bits, formed from a parity check matrix and the transmission data. The receiver corrects errors in the reception data by using the received error correction information, the reception data, and the same parity check matrix. Depending on the information released in this error correction, part of the shared information after correction is discarded, and the remaining information is made to be a shared cryptographic key.
However, if an attempt is made to implement the above-described quantum key distribution in a real world, there are some cases where the above-mentioned error rate is increased due to various factors. Specifically, since information is superimposed on single photons for transmission, many of bits are lost on the way along a transmission line. Consequently, incorrect recognition of a bit-to-bit correspondence is likely to occur between the sender and the receiver. This incorrect recognition causes deterioration in the error rate, and resultantly, generation of a cryptographic key cannot be performed. Hereinafter, a state where synchronization of bit positions is established between Alice and Bob, that is, a state where correct recognition of a bit-to-bit correspondence is established between Alice and Bob, will be referred to as “frame synchronization.” In addition, a state where a bit-to-bit correspondence is incorrectly recognized will be referred to as “frame synchronization deviation,” and the processing for correctly adjusting the state of frame synchronization deviation to the state of frame synchronization will be referred to as “frame synchronization processing.”
As described above, for the sender and receiver to share information, both of the sender and receiver must specify which bit has been correctly detected and which bit has not. In other words, in a quantum key distribution system, it is necessary to establish bit-position synchronization between the sender and receiver. In a key generation flow, it is a precondition that bit-position synchronization is established. If this synchronization is not established, a final key cannot be generated.
However, according to the above-described conventional schemes, there remains a possibility that a loss of frame synchronization occurs due to the extension/contraction of a transmission line and/or a processing deviation inside a device. When a loss of synchronization occurs in a real operation, it is recognized as an eavesdropper being detected, because no sufficient number of check bits match according to the key generation flow described in Japanese Patent Application Unexamined Publication No. 2000-174747. Therefore, bit-position synchronization is established again, and then key generation is carried out. This makes the entire key that has been generated through quantum communication go to waste, extremely degrading the efficiency in generating a shared key. Similarly, according to the method described in Japanese Patent Application Unexamined Publication No. 2004-112278 as well, when bit-position synchronization is lost, the error rate of reception data becomes very large, resulting in it being impossible to generate a shared key. In this publication, no consideration is given to the processing in the case of a large error rate.